Jerry's Log

AVL Tree

Posted: 2026-04-13 Tags: cs datastructure

contents

자료구조의 다음 단계에 오신 것을 환영합니다. 이전 설명에서 우리는 일반적인 이진 탐색 트리(BST)가 가진 치명적인 결함을 확인했습니다: 이미 정렬된 데이터(1, 2, 3, 4, 5)를 삽입하면, 검색 속도가 느린 연결 리스트($O(n)$)로 퇴화해버린다는 점이었죠.

AVL 트리는 1962년 두 명의 소련 수학자 게오르기 아델슨-벨스키(Adelson-Velsky)와 예브게니 란디스(Landis)에 의해 발명되었습니다. 인류 역사상 최초로 만들어진 자가 균형 이진 탐색 트리(Self-Balancing Binary Search Tree) 입니다.

숫자를 삽입하거나 삭제할 때마다 AVL 트리는 스스로의 상태를 점검합니다. 만약 트리의 한쪽이 너무 "무거워지는" 것을 감지하면, 즉각적으로 수학적인 체조(이를 회전, Rotations이라고 부름)를 수행하여 다시 완벽한 균형 상태를 맞춥니다.

내부적으로 이것이 어떻게 작동하는지에 대한 상세한 분석입니다.

1. 핵심 개념: 균형 인수 (Balance Factor)

트리가 언제 균형을 맞춰야 할지 알기 위해, AVL 트리의 모든 노드는 균형 인수(Balance Factor, BF) 라는 특정한 숫자를 계산합니다.

$$\text{균형 인수} = (\text{왼쪽 서브트리의 높이}) - (\text{오른쪽 서브트리의 높이})$$

AVL 절대 규칙:

유효한 AVL 트리에서 _단 하나도 빠짐없이 모든 노드_의 균형 인수는 반드시 -1, 0, 1 중 하나여야 합니다.

만약 단 하나의 노드라도 균형 인수가 2 또는 -2가 된다면, 경고벨이 울립니다. 트리가 공식적으로 불균형 상태가 된 것이며, 즉시 회전(Rotation)이 트리거됩니다.

2. 해결책: 트리 회전 (Tree Rotations)

트리가 불균형해지면, 노드들을 "회전"시켜서 스스로를 고칩니다. 시소를 생각하시면 됩니다. 만약 오른쪽이 너무 무거우면, 시소의 중간을 왼쪽으로 당겨 내려서 오른쪽을 위로 들어 올려야 합니다.

트리가 불균형해지는 시나리오는 정확히 4가지가 있으며, 이를 해결하는 회전 방식도 4가지입니다.

케이스 1: Left-Left (LL) 불균형 $\rightarrow$ 단일 우회전 (Single Right Rotation)

왼쪽 자식의 왼쪽 자식으로 노드를 삽입했을 때 발생합니다.

케이스 2: Right-Right (RR) 불균형 $\rightarrow$ 단일 좌회전 (Single Left Rotation)

오른쪽 자식의 오른쪽 자식으로 노드를 삽입했을 때 발생합니다.

케이스 3: Left-Right (LR) 불균형 $\rightarrow$ 이중 회전 (좌회전 후 우회전)

왼쪽 자식의 오른쪽 자식으로 노드를 삽입했을 때 발생합니다.

케이스 4: Right-Left (RL) 불균형 $\rightarrow$ 이중 회전 (우회전 후 좌회전)

오른쪽 자식의 왼쪽 자식으로 노드를 삽입했을 때 발생합니다.

3. 시간 복잡도: 엄격한 규칙이 주는 이점

AVL 트리는 완벽한 균형을 유지하는 데 집착하기 때문에, 트리의 높이가 수학적으로 항상 $O(\log n)$으로 보장됩니다.

연산 AVL 트리 일반 BST (최악의 경우)
탐색 (Search) $O(\log n)$ $O(n)$
삽입 (Insert) $O(\log n)$ $O(n)$
삭제 (Delete) $O(\log n)$ $O(n)$

AVL 트리에 10억 개의 데이터가 있다고 해도, 특정 데이터를 찾는 데 최대 30단계면 충분합니다. 반면 퇴화된 일반 BST에서는 10억 단계가 걸릴 수 있습니다.

4. AVL 트리 vs. 레드-블랙 트리 (업계 표준)

AVL 트리가 이렇게 완벽하다면, 왜 Java(HashMap, TreeMap)와 C++(std::map)은 대신 레드-블랙 트리(Red-Black Tree) 를 사용할까요?

완벽함에는 대가가 따르기 때문입니다.

경험적 법칙 (Rule of Thumb):

references

Related Posts